'''
开点（动态）线段树， 不预先申请空间，使用left,right数组控制真正的左右指针，真的要用到在申请
适合范围很大，但是操作次数并不多
实际范围大可以考虑离散化
区间add
区间query
'''
import time


class SegmentTree:
    def __init__(self, n: int):
        self.n = n
        # 下一个节点的编号
        self.id = 2
        # 左右指针
        self.left = [0, 0]
        self.right = [0, 0]
        # info sum 数组
        # lazy add 数组
        self.info = [0, 0]
        self.lazy = [0, 0]

    def _build(self, nums):
        # 一定是没有build，如果有build需求，那还怎么动态，一上来就申请完了
        pass

    def _up(self, root):
        self.info[root] = self.info[self.left[root]] + self.info[self.right[root]]

    def _down(self, l, r, root):
        if not self.left[root]:
            self.left[root] = self.id
            self.left.append(0)
            self.right.append(0)
            self.info.append(0)
            self.lazy.append(0)
            self.id += 1
        if not self.right[root]:
            self.right[root] = self.id
            self.left.append(0)
            self.right.append(0)
            self.info.append(0)
            self.lazy.append(0)
            self.id += 1
        if self.lazy[root]:
            mid = (l + r) >> 1
            self._lazy(l, mid, self.left[root], self.lazy[root])
            self._lazy(mid + 1, r, self.right[root], self.lazy[root])
            self.lazy[root] = 0

    def _lazy(self, l, r, root, v):
        self.info[root] += v * (r - l + 1)
        self.lazy[root] += v

    def add(self, L, R, V):
        def f(l, r, root):
            if r < L or l > R: return
            if L <= l and r <= R:
                self._lazy(l, r, root, V)
                return
            self._down(l, r, root)
            mid = (l + r) >> 1
            f(l, mid, self.left[root])
            f(mid + 1, r, self.right[root])
            self._up(root)

        f(1, self.n, 1)

    def query(self, L, R):
        def f(l, r, root):
            if r < L or l > R: return 0
            if L <= l <= r <= R:
                return self.info[root]
            self._down(l, r, root)
            mid = (l + r) >> 1
            return f(l, mid, self.left[root]) + f(mid+1, r, self.right[root])
        return f(1, self.n, 1)





class Right:
    def __init__(self, n):
        self.nums = [0] * n

    def query(self, L, R):
        nums = self.nums
        return sum(nums[L - 1: R])

    def add(self, L, R, V):
        nums = self.nums
        for i in range(L - 1, R):
            nums[i] += V

def test(t_operations=10000, n=1000):
    import random
    c1 = Right(n)
    c2 = SegmentTree(n)
    for _ in range(t_operations):
        op = random.randint(0, 1)
        L, R = random.randint(1, n), random.randint(1, n)
        L, R = min(L, R), max(L, R)
        V = random.randint(0, 100)
        if op == 0:
            s1 = time.time() * 1000
            r1 = c1.query(L, R)
            s2 = time.time() * 1000
            r2 = c2.query(L, R)
            s3 = time.time() * 1000
            if not r1 == r2:
                print('oops')
                break
        else:
            s1 = time.time() * 1000
            c1.add(L, R, V)
            s2 = time.time() * 1000
            c2.add(L, R, V)
            s3 = time.time() * 1000
        print(f'区间[{L}, {R}], 操作。暴力耗时：{s2-s1}ms, 线段树耗时:{s3-s2}')
    print("done")


if __name__ == '__main__':
    test(n=100000)
    # test(n=1000)